/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package huffmanlab;

import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.nio.file.Files;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.SortedSet;
import java.util.Stack;
import java.util.logging.Level;
import java.util.logging.Logger;


/**
 *
 * @author Xearus
 */
public class HuffmanLab {
    
    private static HuffmanTree BuildHuffmanTree(byte[] data) {
        long[] occurenceTable = new long[256]; 
        for(byte b : data) {
            occurenceTable[b & 0xFF]++;
        }
        
        ArrayList<HuffmanTree> trees = new ArrayList<>();
        for(char i = 0; i < 256; i++) {
            if(occurenceTable[i] > 0) {
                HuffmanTree tree = new HuffmanTree();
                tree.Add(Character.valueOf(i), occurenceTable[i]);
                trees.add(tree);
            }
        }
        Comparator<HuffmanTree> weightComparator = new Comparator<HuffmanTree>() {
            @Override
            public int compare(HuffmanTree o1, HuffmanTree o2) {
                if(o1.getWeight() > o2.getWeight())
                    return 1;
                else if(o1.getWeight() < o2.getWeight())
                    return -1;
                else
                    return 0;
            }
        };
        
        while(trees.size() > 1) {
            Collections.sort(trees, weightComparator);
            HuffmanTree left = trees.get(0);
            HuffmanTree right = trees.get(1);
            trees.remove(0);
            right.Add(left);
        }
        
        return trees.get(0);
    }
    
    private static final int BitsForToSkip = 3;
    private static final int BitsForHeaderLength = 17;
    
    private static String SideArrayToPathString(ArrayList<Side> sides) {
        String s = "";
        for(Side side : sides) {
            if(side == Side.Left) {
                s += "0";
            } else {
                s += "1";
            }
        }
        return s;
    }
    
    private static byte[] ByteArrayListToByteArray(ArrayList<Byte> toConvert) {
        byte[] converted = new byte[toConvert.size()];
        for (int i = 0; i < toConvert.size(); i++) {
            converted[i] = toConvert.get(i);
        }
        return converted;
    }
 
    private static Boolean[] SideToBoolean(Side[] sides) {
        Boolean[] field = new Boolean[sides.length];
        for (int i = 0; i < sides.length; i++) {
            field[i] = sides[i] == Side.Right;
        }
        return field;
    }
    
    private static Boolean[] ByteToBooleanArray(int b) {
        Boolean[] field = new Boolean[8];
        field[0] = (b & 0x80) > 0;
        field[1] = (b & 0x40) > 0;
        field[2] = (b & 0x20) > 0;
        field[3] = (b & 0x10) > 0;
        field[4] = (b & 0x08) > 0;
        field[5] = (b & 0x04) > 0;
        field[6] = (b & 0x02) > 0;
        field[7] = (b & 0x01) > 0;
        return field;
    }
    
    private static byte[] Decompress(byte[] compressedData) {
        int headerSize = ((compressedData[0] & 0xFF) << 9);
        headerSize |= ((compressedData[1] & 0xFF) << 1);
        headerSize |= ((compressedData[2] & 0xFF) >>> 7);
        int toSkip = (compressedData[2] >>> 4) & 0x7;
        int posInArray = 2;
        int posInByte = 3;
        int headerBitCount = 0;
        Map<String, Byte> decompressionTable = new HashMap<>();
        Side currentSide = Side.Left;
        ArrayList<Side> path = new ArrayList<>();
        while(headerBitCount < headerSize) {
            boolean bitOn = ((compressedData[posInArray] >> posInByte) & 0x1) > 0;
            path.add(currentSide);
            if(posInByte == 0) {
                posInByte = 7;
                posInArray++;
            } else {
                posInByte--;
            }
            
            if(!bitOn) {
                currentSide = Side.Left;
            } else {
                int value = ((compressedData[posInArray] & 0xFF) << (7 - posInByte)) & 0xFF;
                posInArray++;
                value |= ((compressedData[posInArray] & 0xFF) >> (posInByte + 1)) & 0xFF;
                decompressionTable.put(SideArrayToPathString(path), (byte)value);
                
                Side lastSide;
                do
                {
                    if(path.size() > 0){
                        int lastIndex = path.size() - 1;
                        lastSide = path.get(lastIndex);
                        path.remove(lastIndex);
                    } else {
                      lastSide = Side.Left;  
                    }
                } while (lastSide == Side.Right);
                
                currentSide = Side.Right;
                headerBitCount += 8;
            }
            
            headerBitCount++;
        }
        
        for(int i = 0; i < toSkip; i++) {
            if(posInByte == 0) {
                posInByte = 7;
                posInArray++;
            } else {
                posInByte--;
            }
        }
        ArrayList<Byte> decompressedData = new ArrayList<>();
        
        String readingPath = "";
        while(posInArray < compressedData.length) {
            boolean bitOn = ((compressedData[posInArray] >> posInByte) & 0x1) > 0;
            if(bitOn) {
                readingPath += "1";
            } else {
                readingPath += "0";
            }
            
            if(decompressionTable.containsKey(readingPath)) {
                decompressedData.add(decompressionTable.get(readingPath));
                readingPath = "";
            }
            
            if(posInByte == 0) {
                posInByte = 7;
                posInArray++;
            } else {
                posInByte--;
            }
        }
        
        return ByteArrayListToByteArray(decompressedData);
    }
    
    private static byte[] Compress(byte[] data) {
        HuffmanTree tree = BuildHuffmanTree(data);
        Map<Integer, Side[]> cache = new HashMap<>();
        
        ArrayList<Boolean> header = new ArrayList<>();
        
        Side[] lastCompressedValue = new Side[0]; 
        int nbOfSignificantBits = BitsForHeaderLength + BitsForToSkip;
        for(HuffmanCharacter c : tree) {
            cache.put(c.Value, c.CompressedValue);
            nbOfSignificantBits += c.Weight * c.CompressedValue.length;
            
            int i = 0;
            while(i < lastCompressedValue.length && c.CompressedValue[i] == lastCompressedValue[i])
                i++;
            for (; i < c.CompressedValue.length - 1; i++) {
                header.add(Boolean.FALSE);
            }
            header.add(Boolean.TRUE);
            header.addAll(Arrays.asList(ByteToBooleanArray(c.Value)));
            lastCompressedValue = c.CompressedValue;
        }
        
        
        nbOfSignificantBits += header.size();
        int remaining = Byte.SIZE - (nbOfSignificantBits % Byte.SIZE);
        if(remaining == Byte.SIZE) {
            remaining = 0;
        }
        byte[] compressed = new byte[(nbOfSignificantBits + remaining)/Byte.SIZE];
        
        compressed[0] = (byte)(0xFF & (header.size() >>> 9));
        compressed[1] = (byte)(0xFF & (header.size() >>> 1));
        compressed[2] = (byte)(0x01 & header.size());
        compressed[2] = (byte)(compressed[2] << 3 | (0x07 & remaining));
        int posInByte = 3;
        int posInArray = 2;
        for(Boolean b : header) {
            compressed[posInArray] = (byte)(compressed[posInArray] << 1);
            if(b) {
                compressed[posInArray] |= 0x1;
            }
            if(posInByte == 0) {
                posInByte = 7;
                posInArray++;
            } else {
                posInByte--;
            }
        }
        
        for(int i = 0; i < remaining; i++) {
            compressed[posInArray] = (byte)(compressed[posInArray] << 1);
            if(posInByte == 0) {
                posInByte = 7;
                posInArray++;
            } else {
                posInByte--;
            }
        }
        
        for(byte d : data) {
            for (Boolean b : SideToBoolean(cache.get(d & 0xFF))) {
                compressed[posInArray] = (byte)(compressed[posInArray] << 1);
                if(b) {
                    compressed[posInArray] |= 0x1;
                }
                if(posInByte == 0) {
                    posInByte = 7;
                    posInArray++;
                } else {
                    posInByte--;
                }
            }
        }
        
        return compressed;
    }
    
    private static void prepareCompress(File f){
        //File f = new File("C:\\Users\\Hugo\\Desktop\\log320Huffman\\test86kb.txt");
        byte[] byteContent = null;
        
        try {
            byteContent = Files.readAllBytes(f.toPath());
        } catch (IOException ex) {
            Logger.getLogger(HuffmanLab.class.getName()).log(Level.SEVERE, null, ex);
            return;
        }
        byte[] compressed = Compress(byteContent);
        try {
            try (FileOutputStream out = new FileOutputStream(f.getAbsolutePath() + ".log3")) {
                out.write(compressed);
            }
        } catch (FileNotFoundException ex) {
            System.out.println("Compress File Error");
            Logger.getLogger(HuffmanLab.class.getName()).log(Level.SEVERE, null, ex);
        } catch (IOException ex) {
            System.out.println(" CompressIO Error");
            Logger.getLogger(HuffmanLab.class.getName()).log(Level.SEVERE, null, ex);
        }
    }
    
    private static void prepareDecompress(File f){
        
        try {
            byte[] decompressed = Decompress(Files.readAllBytes(f.toPath()));
            String path = f.getAbsolutePath().substring(0, f.getAbsolutePath().length()-5);
            try (FileOutputStream out = new FileOutputStream(path)) {
                out.write(decompressed);
            }
        } catch (FileNotFoundException ex) {
            System.out.println("Decompress File Error");
            Logger.getLogger(HuffmanLab.class.getName()).log(Level.SEVERE, null, ex);
        } catch (IOException ex) {
            System.out.println("Decompress IO Error");
            Logger.getLogger(HuffmanLab.class.getName()).log(Level.SEVERE, null, ex);
        }
    }
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        if (args.length == 2){
            if (args[0].equals("-compress")){
                    File f = new File(args[1]);
                    prepareCompress(f);
                    System.out.println("Done compressing.");
            }
            else if(args[0].equals("-decompress")){
                File f = new File(args[1]);
                String ext = f.getAbsolutePath().substring(f.getAbsolutePath().length() -4);
                if (ext.equals("log3")){
                    prepareDecompress(f);
                    System.out.println("Done decompressing.");
                }else{
                    System.out.println("Cannot decompress another type than a log3 file.");
                }
                
            }else{
                System.out.println("Wrong arguments were given, arugments gors as follow: -compress FileName or -decompress FileName");
            }
        }
        else{
            System.out.println("Arguments were wrong.");
        }
        
        
        
//        File f = new File("C:\\Users\\Hugo\\Desktop\\log320Huffman\\test86kb.txt");
//        byte[] byteContent = null;
//        
//        try {
//            byteContent = Files.readAllBytes(f.toPath());
//        } catch (IOException ex) {
//            Logger.getLogger(HuffmanLab.class.getName()).log(Level.SEVERE, null, ex);
//            return;
//        }
//        byte[] compressed = Compress(byteContent);
//        try {
//            try (FileOutputStream out = new FileOutputStream("C:\\Users\\Hugo\\Desktop\\log320Huffman\\chat_compressed86")) {
//                out.write(compressed);
//            }
//        } catch (FileNotFoundException ex) {
//            Logger.getLogger(HuffmanLab.class.getName()).log(Level.SEVERE, null, ex);
//        } catch (IOException ex) {
//            Logger.getLogger(HuffmanLab.class.getName()).log(Level.SEVERE, null, ex);
//        }
        
        //byte[] decompressed = Decompress(compressed);
        //try {
        //    try (FileOutputStream out = new FileOutputStream("D://compression/chat_decompressed")) {
        //        out.write(decompressed);
        //    }
        //} catch (FileNotFoundException ex) {
        //    Logger.getLogger(HuffmanLab.class.getName()).log(Level.SEVERE, null, ex);
        //} catch (IOException ex) {
        //    Logger.getLogger(HuffmanLab.class.getName()).log(Level.SEVERE, null, ex);
        //}
        
        
    }
}
